package com.beiding.editanalyzeframe;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author 丁常磊
 * @date 2021/11/30 14:54
 */

public class CommonUtils {
    /**
     * 查找最相似的区间
     * LCS算法
     *
     * @param a
     * @param b
     * @return
     */
    public static List<MaxSameSegment> maxSameSegment(List<Line> a, List<Line> b) {


        if (a.size() == 0 || b.size() == 0) {
            return Collections.emptyList();
        }

        List<MaxSameSegment> r = new ArrayList<>();

        int len1 = a.size();
        int len2 = b.size();


        //下一行的值  伸展一列, 可接受右侧边缘的值
        int[] currentLineValue = new int[len2 + 1];
        int[] nextLienValue = new int[len2 + 1];

        //初始化为0
        for (int i = 0; i < nextLienValue.length; i++) {
            nextLienValue[i] = 0;
        }

        /*
            只需要走一遍即可. 不需要反复执行
         */

        for (int i = 0; i < len1; i++) {

//            System.out.println("当前行:" + i);

            int[] tmp = currentLineValue;

            //切换为下一行的值
            currentLineValue = nextLienValue;

            nextLienValue = tmp;

            //本行中最大的数字
            int maxValue = 0;

            int mj = -1;

            for (int j = 0; j < len2; j++) {
                //如果相等
                if (a.get(i).eq(b.get(j))) {
                    //给当前坐标添加值

                    //获取当前行的值. 当前行的值,可能由上一行初始化(初始化为同上一行的值)
                    int currentValue = currentLineValue[j];

                    int cv = currentValue + 1;

                    //把当前的值传递到下一行
                    nextLienValue[j + 1] = cv;

                } else {

                    //上一行初始化的值
                    int v = currentLineValue[j];

                    //大于0表示在当前行之前的行都是相等的
                    if (v > 0) {

                        //取最大
                        if (v > maxValue) {

                            mj = j;

                            maxValue = v;
                        }

                    }

                    //下一行的值为0
                    nextLienValue[j + 1] = 0;

                }

//                System.out.print("\t" + nextLienValue[j]);

            }


            //识别一次边界值
            int v = currentLineValue[len2];

            //大于0表示在当前行之前的行都是相等的
            if (v > 0) {

                //取最大
                if (v > maxValue) {

                    mj = len2;

                    maxValue = v;
                }

            }

            if (mj != -1) {

                //确定了最大

                MaxSameSegment maxSameSegment = new MaxSameSegment();

                maxSameSegment.len = maxValue;
                maxSameSegment.startA = i - maxSameSegment.len;
                maxSameSegment.startB = mj - maxSameSegment.len;

                r.add(maxSameSegment);

            }

//            System.out.print("\t" + nextLienValue[len2]);
//            System.out.println();

        }

        //最后一次收尾判断


        //本行中最大的数字
        int maxValue = 0;

        int mj = -1;

        currentLineValue = nextLienValue;

        for (int j = 0; j < currentLineValue.length; j++) {
            //上一行初始化的值
            int v = currentLineValue[j];

            //大于0表示在当前行之前的行都是相等的
            if (v > 0) {

                //取最大
                if (v > maxValue) {

                    mj = j;

                    maxValue = v;
                }

            }
        }

        if (mj != -1) {

            //确定了最大

            MaxSameSegment maxSameSegment = new MaxSameSegment();

            maxSameSegment.len = maxValue;
            maxSameSegment.startA = len1 - maxSameSegment.len;
            maxSameSegment.startB = mj - maxSameSegment.len;

            r.add(maxSameSegment);

        }

        //先按照重合长度排序 按照
        SortUtils.sort(r, (w, z) -> {

            int v = z.len - w.len;

            if (v == 0) {
                v = w.getStartA() - z.getStartA();
                if (v == 0) {
                    v = w.getStartB() - z.getStartB();
                }
            }

            return v;

        });

        //向后检查交叉
        for (int i = 0; i < r.size(); i++) {

            MaxSameSegment maxSameSegment = r.get(i);

            for (int j = i + 1; j < r.size(); ) {

                MaxSameSegment check = r.get(j);
                if (

                    //横坐标交叉
                        check.getStartA() >= maxSameSegment.getStartA() && check.getStartA() < maxSameSegment.getStartA() + maxSameSegment.getLen()
                                ||
                                //纵坐标交叉
                                check.getStartB() >= maxSameSegment.getStartB() && check.getStartB() < maxSameSegment.getStartB() + maxSameSegment.getLen()
                ) {
                    r.remove(j);
                } else {
                    j++;
                }

            }

        }

        SortUtils.sort(r, (w, z) -> {

            return w.getStartA() - z.getStartA();

        });

        return r;

    }

    /**
     * 寻找最大相似性
     *
     * @param a
     * @param b
     * @return
     */
    public static MaxEditPossibilityResult maxEditPossibility(List<Line> a, List<Line> b,AnalyzeConfig analyzeConfig) {

        //最大编辑可能性
        /*
            进行相似度最大且无交叉连线
            1. 计算连线的相似度
                相似度评分公式
                    = 2*最大连续重复文字数/(A串字数+B串字数)
            2. 计算无交叉连线最大相似度
                右下节点求和最大的所有节点
         */

        List<MaxLineCombination> maxPoints = new ArrayList<>();

        //先计算所有的排列组合可能性
        for (int i = 0; i < a.size(); i++) {
            for (int j = 0; j < b.size(); j++) {

                //每个点都是最大可能性点
                Line la = a.get(i);
                Line lb = b.get(j);

                //计算编辑的可能性
                double v = analyzeConfig.getEditPossibility().editPossibility(la.getText(), lb.getText());

                //如果可能性大于0
                if (v > 0) {
                    MaxLineCombination maxPoint = new MaxLineCombination();
                    maxPoint.x = i;
                    maxPoint.y = j;
                    maxPoint.v = v;
                    maxPoint.sumV = v;
                    maxPoint.al = la;
                    maxPoint.bl = lb;
                    maxPoints.add(maxPoint);
                }

            }
        }

        if (maxPoints.size() == 0) {
            return new MaxEditPossibilityResult();
        }

        //进行闭包排序
        SortUtils.sort(maxPoints, (pa, pb) -> {

            //闭包计算
            if (pb.x > pa.x) {
                return -1;
            } else if (pa.x > pb.x) {
                return 1;
            }

            if (pb.y > pa.y) {
                return -1;
            } else if (pa.y > pb.y) {
                return 1;
            }

            //其余不关注
            return 0;
        });


        //最大相似值
        double max = 0;

        MaxLineCombination maxLinePoint = null;

        for (int i = 0; i < maxPoints.size(); i++) {

            //当前的行结合
            MaxLineCombination current = maxPoints.get(i);

            //寻找前置完全可以闭包且最大的节点
            MaxLineCombination maxPre = null;
            for (int j = i - 1; j >= 0; j--) {
                MaxLineCombination check = maxPoints.get(j);
                //可以完全闭包
                if (current.x > check.x && current.y > check.y) {
                    if (maxPre == null) {
                        maxPre = check;
                    } else {
                        if (check.sumV > maxPre.sumV) {
                            maxPre = check;
                        }
                    }
                }
            }
            if (maxPre != null) {
                //将前置数数字累加到自身
                current.sumV = current.v + maxPre.sumV;
                //记录前置行
                current.pre = maxPre;
            }
            if (current.sumV > max) {
                maxLinePoint = current;
                max = current.sumV;
            }

        }

        //找到最大组合

        //倒叙得到最大组合

        MaxEditPossibilityResult maxEditPossibilityResult = new MaxEditPossibilityResult();
        while (maxLinePoint != null) {
            LinePair editLinePair = new LinePair(maxLinePoint.al, maxLinePoint.bl);
            maxEditPossibilityResult.editLinePairs.add(0, editLinePair);
            maxLinePoint = maxLinePoint.pre;
        }
        return maxEditPossibilityResult;

    }

    /**
     * 最大行结合
     */
    private static class MaxLineCombination {

        //可能性的值
        private double v;
        //可能性加和
        private double sumV;
        //左侧的行
        private int x;
        //右侧的行
        private int y;
        //左侧的行
        private Line al;
        //右侧的行
        private Line bl;

        private MaxLineCombination pre;

    }


    public static class MaxEditPossibilityResult {

        private List<LinePair> editLinePairs = new ArrayList<>();

        public List<LinePair> getEditLinePairs() {
            return editLinePairs;
        }

    }

    public static class MaxSameSegment {
        private int startA;
        private int startB;
        private int len;

        public int getStartA() {
            return startA;
        }

        public int getStartB() {
            return startB;
        }

        public int getLen() {
            return len;
        }
    }

}
